<!-------- @HEADER
 !
 ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 !
 !  Zoltan Toolkit for Load-balancing, Partitioning, Ordering and Coloring
 !                  Copyright 2012 Sandia Corporation
 !
 ! Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
 ! the U.S. Government retains certain rights in this software.
 !
 ! Redistribution and use in source and binary forms, with or without
 ! modification, are permitted provided that the following conditions are
 ! met:
 !
 ! 1. Redistributions of source code must retain the above copyright
 ! notice, this list of conditions and the following disclaimer.
 !
 ! 2. Redistributions in binary form must reproduce the above copyright
 ! notice, this list of conditions and the following disclaimer in the
 ! documentation and/or other materials provided with the distribution.
 !
 ! 3. Neither the name of the Corporation nor the names of the
 ! contributors may be used to endorse or promote products derived from
 ! this software without specific prior written permission.
 !
 ! THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
 ! EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 ! IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 ! PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
 ! CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 ! EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 ! PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 ! PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 ! LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 ! NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 ! SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 !
 ! Questions? Contact Karen Devine	kddevin@sandia.gov
 !                    Erik Boman	egboman@sandia.gov
 !
 ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 !
 ! @HEADER
-------> 
<HTML>
<HEAD>
   <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
   <META NAME="GENERATOR" CONTENT="Mozilla/4.04 [en] (X11; U; SunOS 5.6 sun4m) [Netscape]">

  <meta name="sandia.approval_type" content="formal">
  <meta name="sandia.approved" content="SAND2007-4748W">
  <meta name="author" content="Zoltan PI">

   <TITLE>Zoltan User's Guide:  Octree Partitioning</TITLE>
</HEAD>
<BODY BGCOLOR="#FFFFFF">

<div ALIGN=right><b><i><a href="ug.html">Zoltan User's Guide</a>&nbsp; |&nbsp; <a href="ug_order.html">Next</a>&nbsp; |&nbsp; <a href="ug_alg_patoh.html">Previous</a></i></b></div>


<H2>
<A NAME="Octree"></A>Octree Partitioning (OCTPART)</H2>
The Octree Partitioning algorithm is based upon work in load balancing
for parallel mesh generation at Rensselaer Polytechnic Institute [<A HREF="ug_refs.html#flaherty">Flaherty,
Loy et al.</A>]. It was implemented in Zoltan by Luis Gervasio, Department
of Computer Science, Rensselaer Polytechnic Institute, as his summer project
in 1998 [<A HREF="ug_refs.html#gervasio">Gervasio</A>].  An octree is a spatial
decomposition of the computational domain in which the root of the tree,
representing the entire domain, is recursively divided by two in each coordinate
direction (producing eight or four "child" octants in 3D or 2D, respectively)
until each subregion holds at most an application-specified number of objects.
These subregions are represented by the leaves of the octree. The octree
data structure is widely used in mesh generation and adaptive mesh refinement
[<U><A HREF="ug_refs.html#baehmann">Baehmann et al.</A></U>, <U><A HREF="ug_refs.html#shephard">Shephard
and Georges</A></U>].  The octree resulting from such a spatial decomposition
of the domain can be used to partition an application's work [<A HREF="ug_refs.html#edwards">Edwards</A>,
<A HREF="ug_refs.html#pilkington">Pilkington and Baden</A>, <A HREF="ug_refs.html#warren">Warren
and Salmon</A>]. To partition an octree, a traversal of the tree is used
to define a global ordering on the leaves of the octree. This global ordering
is often referred to as a Space-Filling Curve (SFC). The leaves of the
octree can be easily assigned to processors in a manner which equally distributes
work by assigning slices of the ordered list to processors. Different tree-traversal
algorithms produce different global orderings or SFCs, with some SFCs having
better connectivity and partition quality properties than others. Currently,
Morton Indexing (i.e., Z-curve), Grey Code, and Hilbert SFCs are supported.
Morton Indexing and Grey Code SFCs are the simplest (and currently, the
fastest) of the SFC algorithms, but they produce lower-quality partitions
than the Hilbert SFC. 
<BR>&nbsp;
<TABLE WIDTH="100%" NOSAVE >
<TR>
<TD VALIGN=TOP><B>Method String:</B></TD>

<TD><B>OCTPART</B></TD>
</TR>

<TR>
<TD><B>Parameters:</B></TD>

<TD></TD>
</TR>

<TR>
<TD VALIGN=TOP>&nbsp;&nbsp;&nbsp; <I>OCT_DIM</I></TD>

<TD>Specifies whether the 2D or 3D Octree algorithms should be used. The
3D algorithms can be used for 2D problems, but much memory will be wasted
to allow for a non-existent third dimension. Similarly, a 2D algorithm
can be used for 3D surface meshes provided that the surface can be projected
to the <I>xy</I>-plane without overlapping points.&nbsp;
<BR>2 = use 2D algorithm; 3 = use 3D algorithm.</TD>
</TR>

<TR>
<TD VALIGN=TOP><I>&nbsp;&nbsp;&nbsp; OCT_METHOD</I></TD>

<TD>The SFC to be used.&nbsp;
<BR>0 = Morton Indexing; 1 = Grey Code; 2 = Hilbert.</TD>
</TR>

<TR>
<TD VALIGN=TOP>&nbsp;&nbsp;&nbsp; <I>OCT_MINOBJECTS</I></TD>

<TD>The minimum number of objects to allow in a leaf octant of the octree.
These objects will be assigned as a group to a processor, so this parameter
helps define the granularity of the load-balancing problem.  Values greater than
or equal to one are allowable.</TD>
</TR>
<TR>
<TD VALIGN=TOP>&nbsp;&nbsp;&nbsp; <I>OCT_MAXOBJECTS</I></TD>

<TD>The maximum number of objects to allow in a leaf octant of the octree.
These objects will be assigned as a group to a processor, so this parameter
helps define the granularity of the load-balancing problem.  Values greater than
or equal to one are allowable.</TD>
</TR>

<TR>
<TD VALIGN=TOP>&nbsp;&nbsp;&nbsp; <I>OCT_OUTPUT_LEVEL</I></TD>

<TD>Amount of output the load-balancing algorithm should produce.&nbsp;
<BR>0 = no statistics; 1 = statistics summary; 2 = debugging information; 3 = data for generating plots.</TD>
</TR>

<TR>
<TD VALIGN=TOP><B>Default:</B></TD>

<TD></TD>
</TR>

<TR>
<TD></TD>

<TD><I>OCT_DIM</I> = 3</TD>
</TR>

<TR>
<TD></TD>

<TD><I>OCT_METHOD</I> = 2</TD>
</TR>

<TR>
<TD></TD>

<TD><I>OCT_MINOBJECTS</I> = 10</TD>
</TR>
<TR>
<TD></TD>

<TD><I>OCT_MAXOBJECTS</I> = 40</TD>
</TR>

<TR>
<TD></TD>

<TD><I>OCT_OUTPUT_LEVEL</I> = 0</TD>
</TR>

<TR>
<TD VALIGN=TOP><B>Required Query Functions:</B></TD>

<TD></TD>
</TR>

<TR>
<TD></TD>

<TD><B><A HREF="ug_query_lb.html#ZOLTAN_NUM_OBJ_FN">ZOLTAN_NUM_OBJ_FN</A></B></TD>
</TR>

<TR>
<TD></TD>

<TD><B><A HREF="ug_query_lb.html#ZOLTAN_OBJ_LIST_FN">ZOLTAN_OBJ_LIST_FN</A></B>
</TD>
</TR>

<TR>
<TD></TD>

<TD><B><A HREF="ug_query_lb.html#ZOLTAN_NUM_GEOM_FN">ZOLTAN_NUM_GEOM_FN</A></B></TD>
</TR>

<TR>
<TD></TD>

<TD>
<b><a href="ug_query_lb.html#ZOLTAN_GEOM_MULTI_FN">ZOLTAN_GEOM_MULTI_FN</a></b>
or <b><a href="ug_query_lb.html#ZOLTAN_GEOM_FN">ZOLTAN_GEOM_FN</a></b>
</TD>
</TR>
</TABLE>
&nbsp;

<P>
<HR WIDTH="100%">[<A HREF="ug.html">Table of Contents</A>&nbsp; |&nbsp;
<A HREF="ug_order.html">Next:&nbsp; Ordering </A>&nbsp;
|&nbsp; <A HREF="ug_alg_patoh.html">Previous:&nbsp;&nbsp; ParKway</A>&nbsp; |&nbsp; <a href="https://www.sandia.gov/general/privacy-security/index.html">Privacy and Security</a>]
</BODY>
</HTML>
